package easy;

import javax.swing.tree.TreeNode;

/**
 * 1379. 找出克隆二叉树中的相同节点
 * 创建时间：2024-04-03 15:17
 */
public class 找出克隆二叉树中的相同节点_1379 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    /**
     * 二叉树遍历的三种方式
     * 1. 前序遍历 根左右
     * 2. 中序遍历 左根右
     * 3. 后序遍历 左右根
     * 前中后指的是根的位置
     */
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        // 如果为空直接返回
        if(original == null){
            return null;
        }
        // 首先比较根节点
        if(original == target){
            return cloned;
        }

        // 再比较左节点
        TreeNode left = getTargetCopy(original.left, cloned.left, target);
        if(left != null) {
            return left;
        }
        // 再比较右节点
        return getTargetCopy(original.right, cloned.right, target);
    }
}
